package geekstudy.week7;

/**
 *
 * 684. 冗余连接
 * https://leetcode-cn.com/problems/redundant-connection/
 *
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：1 ms, 在所有 Java 提交中击败了88.27% 的用户
 * 内存消耗：38.6 MB, 在所有 Java 提交中击败了72.51% 的用户
 *
 *
 */
public class Week7RedundantConnection {

    public int[] findRedundantConnection(int[][] edges) {
        if(edges == null || edges.length == 0) {
            return new int[0];
        }

        int delete = -1;
        UnionFindSets unionFindSets = new UnionFindSets(edges.length);
        for(int size=0; size<edges.length; size++){
            int firstPoint = edges[size][0];
            int secondPoint = edges[size][1];
            if(unionFindSets.connect(firstPoint, secondPoint)){
                delete = size;
            }else{
                unionFindSets.union(firstPoint, secondPoint);
            }
        }
        return edges[delete];
    }


    class UnionFindSets{

        private int[] findArray;

        UnionFindSets(int n){
            findArray = new int[n+1];
            for(int size = 1; size< n+1; size++){
                findArray[size] = size;
            }
        }

        public int find(int value){
            int root = value;
            while(root != findArray[root]){
                root = findArray[root];
            }
            while(value != findArray[value]){
                int temp = findArray[value];
                findArray[value] = root;
                value = temp;
            }
            return root;
        }

        public void union(int first,int second){
            int firstFind = find(first);
            int secondFind = find(second);
            if(firstFind == secondFind){
                return;
            }
            findArray[firstFind] = secondFind;
        }

        public boolean connect(int first,int second){
            return find(first) == find(second);
        }

    }
}
